package com.kevinkk.tree;

import java.util.*;

/**
 * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
 */

/**
 * 这道题需要进行回溯
 * 其实所有的递归都是带有回溯的，但是这道题需要进行显式的回溯、删除遍历过的节点
 */

public class BinaryTreePaths {
    class Solution {
        List<String> res = new ArrayList<>();

        public List<String> binaryTreePaths(TreeNode root) {
            traversal(root, new ArrayList<Integer>());
            return res;
        }

        private void traversal(TreeNode node, List<Integer> list){
            list.add(node.val);
            if(node.left == null && node.right == null){
                StringBuilder sb = new StringBuilder();
                for(int i : list)
                    sb.append(i + "->");
                // StringBuilder 进行删除时分别使用的是 delete 和 deleteCharAt
                sb.delete(sb.length()-2, sb.length());
                res.add(sb.toString());
                return;
            }
            if(node.left != null){
                traversal(node.left, list);
                // list 进行删除时使用的是 remove
                list.remove(list.size()-1);
            }
            if(node.right != null){
                traversal(node.right, list);
                list.remove(list.size()-1);
            }
        }
    }
}
